<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>Math_Goldbach_conjecture</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h1 id="toc-0">哥德巴赫猜想</h1>
<p>一个著名的数学定理.</p>
<h3 id="toc-1">命题A：任何≥6的偶数可以拆为两个(奇)素数之和.</h3>
<h3 id="toc-2">命题B：任何≥9的奇数可以拆为3个(奇)素数之和.</h3>
<p>因为如果命题A成立，命题B必然成立，所以大多数的时候都提出命题A.</p>
<p>这个问题俗称为1+1问题.</p>
<p>就是任何≥6的偶数可以拆为两个(奇)素数之和的意思.</p>
<p>现设N是偶数，虽然不能证明N是两个素数之和，但足以证明它能够写成两个殆素数的和，即N=A+B，其中A和B的素因子个数都不太多，譬如说素因子个数不超过10.</p>
<p>用“a+b”来表示如下命题：每个大偶数N都可表为A+B，其中A和B的素因子个数分别不超过a和b.显然，哥德巴赫猜想就可以写成"1+1".在这一方向上的进展都是用所谓的筛法得到的.</p>
<pre><code>“a + b”问题的推进
1920年，挪威的布朗证明了“9 + 9”.
1924年，德国的拉特马赫证明了“7 + 7”.
1932年，英国的埃斯特曼证明了“6 + 6”.
1937年，意大利的蕾西先后证明了“5 + 7”, “4 + 9”, “3 + 15”和“2 + 366”.
1938年，苏联的布赫夕太勃证明了“5 + 5”.
1940年，苏联的布赫夕太勃证明了“4 + 4”.
1956年，中国的王元证明了“3 + 4”.稍后证明了 “3 + 3”和“2 + 3”.
1948年，匈牙利的瑞尼证明了“1+ c”，其中c是一很大的自然数.
1962年，中国的潘承洞和苏联的巴尔巴恩证明了“1 + 5”， 中国的王元证明了“1 + 4”.
1965年，苏联的布赫 夕太勃和小维诺格拉多夫，及意大利的朋比利证明了“1 + 3 ”.
1966年，中国的陈景润证明了 “1 + 2 ”.</code></pre>
<p>对此，我们产生了很浓厚的兴趣，也许并不能真正的证明出哥德巴赫猜想，但是我们想利用计算机高效的计算效率，帮助验证<strong>一定范围内的数字是否符合哥德巴赫猜想</strong></p>
<p>具体可以到2^63-1大小的数字，显然对于后面的而言并不能做到，但是如果结合上高精度算法可以算到近100000000位的数字的大小，但是并不能保证时间和空间的效率最大化，以下代码和思路的检验方法可以保证在1s以内算出答案，并且对计算机的配置要求很低.</p>
<p>学习了一部分的计算机知识之后，我们简略地写出了第一份较为简单的代码.</p>
<div class="highlight"><pre><span></span><span class="c1">//By:yx</span>
<span class="c1">//2017.4.30.</span>
<span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;ctime&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span> <span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">bool</span> <span class="n">Prime</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">)</span> <span class="p">{</span><span class="c1">//判断是否为质数的函数  </span>
    <span class="kt">int</span> <span class="n">j</span><span class="p">;</span>  
    <span class="k">if</span> <span class="p">(</span><span class="n">i</span><span class="o">&lt;=</span><span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span><span class="c1">//如果小于等于1返回0  </span>
    <span class="k">if</span> <span class="p">(</span><span class="n">i</span><span class="o">==</span><span class="mi">2</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span><span class="c1">//如果是2，返回1  </span>
    <span class="k">for</span><span class="p">(</span><span class="n">j</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">i</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span><span class="c1">//循环遍历判断是否为质数  </span>
        <span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="o">%</span><span class="n">j</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>  
        <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">i</span><span class="o">!=</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span>  
        <span class="k">else</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>  
    <span class="p">}</span>  

<span class="p">}</span>  
<span class="kt">int</span> <span class="n">main</span><span class="p">()</span> <span class="p">{</span>  
    <span class="kt">long</span> <span class="kt">long</span> <span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">f1</span><span class="p">,</span><span class="n">f2</span><span class="p">,</span><span class="n">n</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">;</span>  
    <span class="n">puts</span><span class="p">(</span><span class="s">&quot;请输入要验证的偶数范围,即输入两个正偶数&quot;</span><span class="p">);</span>  
    <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%lld%lld&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">a</span><span class="p">,</span><span class="o">&amp;</span><span class="n">b</span><span class="p">);</span>  
    <span class="kt">long</span> <span class="kt">long</span> <span class="n">minn</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">);</span><span class="c1">//求较小的数  </span>
    <span class="kt">long</span> <span class="kt">long</span> <span class="n">maxx</span><span class="o">=</span><span class="n">max</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">);</span><span class="c1">//求较大的数  </span>
    <span class="k">for</span> <span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="n">min</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">max</span><span class="p">;</span><span class="n">i</span><span class="o">+=</span><span class="mi">2</span><span class="p">)</span> <span class="p">{</span><span class="c1">//偶数相加  </span>
        <span class="k">for</span> <span class="p">(</span><span class="n">k</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span><span class="n">k</span><span class="o">&lt;=</span><span class="n">i</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span><span class="n">k</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span><span class="c1">//根据鸽笼定理，将偶数分为两部分  </span>
            <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="o">-</span><span class="n">k</span><span class="p">;</span><span class="c1">//另一部分  </span>
            <span class="n">flag1</span><span class="o">=</span><span class="n">Prime</span><span class="p">(</span><span class="n">k</span><span class="p">);</span>
            <span class="k">if</span><span class="p">(</span><span class="n">f1</span><span class="p">){</span><span class="c1">//如果k为质数  </span>
                <span class="n">f2</span> <span class="o">=</span> <span class="n">Prime</span><span class="p">(</span><span class="n">j</span><span class="p">);</span>  
                <span class="k">if</span><span class="p">(</span><span class="n">f2</span><span class="p">){</span><span class="c1">//j也为质数  </span>
                    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d=%d+%d &quot;</span><span class="p">,</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">k</span><span class="p">);</span> 
                    <span class="n">n</span><span class="o">++</span><span class="p">;</span>  
                    <span class="k">if</span> <span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="mi">5</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span> <span class="n">puts</span><span class="p">(</span><span class="s">&quot;&quot;</span><span class="p">);</span><span class="c1">//每5个换行 </span>
                    <span class="k">break</span><span class="p">;</span>  
                <span class="p">}</span>  
            <span class="p">}</span>  
        <span class="p">}</span>  
    <span class="p">}</span>  
    <span class="k">if</span> <span class="p">(</span><span class="n">n</span><span class="o">==</span><span class="p">(</span><span class="n">max</span><span class="o">-</span><span class="n">min</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="n">puts</span><span class="p">(</span><span class="s">&quot;哥德巴赫猜想正确！&quot;</span><span class="p">);</span><span class="c1">//如果个数满足要求输出猜想正确  </span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>  
<span class="p">}</span>
</pre></div>
<p>在一段时间的学习之后，有一种更为高效的对于这个程序的做法.</p>
<p>对于程序的优化，想要尽可能的大的判断较少个数是否符合哥德巴赫猜想，可以引用费马小定理.</p>
<h6 id="toc-3">也就是常说的Miller_Rabin素数判定</h6>
<p>对于需要一个范围的数字判断是否符合哥德巴赫猜想，可以使用一般的枚举算法，枚举每一个数字，显然这样会到时程序的运行时间过长.</p>
<p>可以在这个的基础上进行一些小优化，尤其是对于素数的判定.</p>
<p>1) 埃拉托斯特尼筛法.</p>
<p>2) 线性筛.</p>
<div class="highlight"><pre><span></span><span class="c1">//By:yx</span>
<span class="c1">//2017.08.12 埃氏筛</span>
<span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;ctime&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span> <span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span><span class="p">;</span>
<span class="p">}</span>

<span class="k">static</span> <span class="kt">bool</span> <span class="n">IsPrimeNumber</span><span class="p">(</span><span class="kt">int</span> <span class="n">intNum</span><span class="p">)</span>  
<span class="p">{</span>  
    <span class="kt">bool</span> <span class="n">blFlag</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span><span class="c1">//标识是否是素数  </span>
    <span class="k">if</span><span class="p">(</span><span class="n">intNum</span><span class="o">==</span><span class="mi">1</span><span class="o">||</span><span class="n">intNum</span><span class="o">==</span><span class="mi">2</span><span class="p">)</span><span class="c1">//判断输入的数字是否是1或者2  </span>
    <span class="n">blFlag</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span><span class="c1">//为bool类型变量赋值  </span>
    <span class="k">else</span><span class="p">{</span>  
        <span class="kt">int</span> <span class="n">sqr</span><span class="o">=</span><span class="p">(</span><span class="kt">int</span><span class="p">)(</span><span class="n">sqrt</span><span class="p">((</span><span class="kt">double</span><span class="p">)</span><span class="n">intNum</span><span class="p">));</span>   <span class="c1">//对要判断的数字进行开方运算  </span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">sqr</span><span class="p">;</span><span class="n">i</span><span class="o">&gt;=</span><span class="mi">2</span><span class="p">;</span><span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">intNum</span><span class="o">%</span><span class="n">i</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span> <span class="n">bfFlag</span><span class="o">=</span><span class="nb">false</span><span class="p">;</span><span class="c1">//从开方后的数进行循环,对要判断的数字和指定数字进行求余运算,如果余数为0，说明不是素数  </span>
    <span class="p">}</span>  
    <span class="k">return</span> <span class="n">blFlag</span><span class="p">;</span><span class="c1">//返回bool型变量  </span>
<span class="p">}</span>

<span class="k">static</span> <span class="kt">bool</span> <span class="n">ISGDBHArith</span><span class="p">(</span><span class="kt">int</span> <span class="n">intNum</span><span class="p">)</span>  
<span class="p">{</span>  
    <span class="kt">bool</span> <span class="n">blFlag</span><span class="o">=</span><span class="nb">false</span><span class="p">;</span><span class="c1">//标识是否符合哥德巴赫猜想  </span>
    <span class="k">if</span><span class="p">(</span><span class="n">intNum</span><span class="o">%</span><span class="mi">2</span><span class="o">==</span><span class="mi">0</span><span class="o">&amp;&amp;</span><span class="n">intNum</span><span class="o">&gt;</span><span class="mi">6</span><span class="p">)</span><span class="c1">//对要判断的数字进行判断 </span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">intNum</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>  
            <span class="kt">bool</span> <span class="n">bl1</span><span class="o">=</span><span class="n">IsPrimeNumber</span><span class="p">(</span><span class="n">i</span><span class="p">);</span><span class="c1">//判断i是否为素数  </span>
            <span class="kt">bool</span> <span class="n">bl2</span><span class="o">=</span><span class="n">IsPrimeNumber</span><span class="p">(</span><span class="n">intNum</span><span class="o">-</span><span class="n">i</span><span class="p">);</span><span class="c1">//判断intNum-i是否为素数  </span>
            <span class="k">if</span><span class="p">(</span><span class="n">bl1</span><span class="o">&amp;</span><span class="n">bl2</span><span class="p">){</span><span class="c1">//输出等式  </span>
                <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d=%d+%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">intNum</span><span class="p">,</span><span class="n">i</span><span class="p">,</span><span class="n">intNum</span><span class="o">-</span><span class="n">i</span><span class="p">);</span>  
                <span class="n">blFlag</span><span class="o">=</span><span class="nb">true</span><span class="p">;</span><span class="c1">//break;符合哥德巴赫猜想  </span>
            <span class="p">}</span>  
        <span class="p">}</span>  
    <span class="k">return</span> <span class="n">blFlag</span><span class="p">;</span><span class="c1">//返回bool型变量  </span>
<span class="p">}</span>  

<span class="kt">int</span> <span class="n">main</span><span class="p">()</span>  
<span class="p">{</span>  
    <span class="kt">int</span> <span class="n">a</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>  
    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;输入一个大于6的偶数:</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">);</span>  
    <span class="n">scanf_s</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">a</span><span class="p">,</span><span class="mi">10</span><span class="p">);</span>  
    <span class="kt">bool</span> <span class="n">blFlag</span><span class="o">=</span><span class="n">ISGDBHArith</span><span class="p">(</span><span class="n">a</span><span class="p">);</span><span class="c1">//判断是否符合哥德巴赫猜想  </span>
    <span class="k">if</span><span class="p">(</span><span class="n">blFlag</span><span class="p">)</span> <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d能写成两个素数的和,所以其符合哥德巴赫猜想.&quot;</span><span class="p">,</span><span class="n">a</span><span class="p">);</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>如果我们只是检验一个数的话，我们用以下这种方法会得到更良好友善的答案.</p>
<h4 id="toc-4">费马小定理</h4>
<p>过程：</p>
<p>1) 计算奇数M，使得 (N=2^r*M+1)</p>
<p>2) 选择随机数A&lt;N.</p>
<p>3) 对于任意i&lt;r，如果满足下面的式子就说明N通过了随机数A的测试.</p>
<p>[A^{2^i+M}modN=N-1]</p>
<p>4) 或者如果满足下面的式子，就说明N通过了随机数A的测试.</p>
<p>[A^MmodN=1]</p>
<p>5) 让A取不同的值对N进行测试，例如测试5次，如果每次都通过，那么就说明N是一个素数.</p>
<p>如果N通过一次测试，那么N不是素数的概率为25%，若N通过t次测试，就说明N不是素数的概率为:</p>
<p>[P=\frac{1}{4^t}]</p>
<p>如果P已经小于一个很小很小的值的时候，就可以说明这个数是一个质数.</p>
<p>对于程序实现的一些优化:</p>
<p>我们可以让A是一个小质数，可以提升这个不是素数的概率，同时让r=0，我们可以直接进行第3步判断，可以进一步提升测试速度.</p>
<div class="highlight"><pre><span></span><span class="c1">//Miller_Rabin</span>
<span class="c1">//2017.10.1</span>
<span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;ctime&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span> <span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="n">modular_exp</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span><span class="kt">int</span> <span class="n">m</span><span class="p">,</span><span class="kt">int</span> <span class="n">n</span><span class="p">){</span>
    <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">m</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">if</span><span class="p">(</span><span class="n">m</span><span class="o">==</span><span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="n">a</span><span class="o">%</span><span class="n">n</span><span class="p">;;</span>
    <span class="kt">long</span> <span class="kt">long</span> <span class="n">w</span><span class="o">=</span><span class="n">modular_exp</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">m</span><span class="o">/</span><span class="mi">2</span><span class="p">,</span><span class="n">n</span><span class="p">);</span>
    <span class="n">w</span><span class="o">=</span><span class="n">w</span><span class="o">*</span><span class="n">w</span><span class="o">%</span><span class="n">n</span><span class="p">;</span><span class="k">if</span><span class="p">(</span><span class="n">m</span><span class="o">&amp;</span><span class="mi">1</span><span class="p">)</span> <span class="n">w</span><span class="o">=</span><span class="n">w</span><span class="o">*</span><span class="n">a</span><span class="o">%</span><span class="n">n</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">w</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">bool</span> <span class="n">Miller_Rabin</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">){</span>
    <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">==</span><span class="mi">2</span><span class="p">)</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">cout</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">a</span><span class="o">=</span><span class="n">rand</span><span class="p">()</span><span class="o">%</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">2</span><span class="p">)</span><span class="o">+</span><span class="mi">2</span><span class="err">；</span>
        <span class="k">if</span><span class="p">(</span><span class="n">modular_exp</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">)</span><span class="o">!=</span><span class="n">a</span><span class="p">)</span> <span class="k">return</span> <span class="nb">false</span> <span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">srand</span><span class="p">(</span><span class="n">time</span><span class="p">(</span><span class="mi">0</span><span class="p">));</span>
    <span class="kt">int</span> <span class="n">t</span><span class="p">;</span><span class="n">read</span><span class="p">(</span><span class="n">t</span><span class="p">);</span>
    <span class="k">while</span><span class="p">(</span><span class="n">t</span><span class="o">--</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">n</span><span class="p">;</span><span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">);</span>
        <span class="k">if</span><span class="p">(</span><span class="n">Miller_Rabin</span><span class="p">(</span><span class="n">n</span><span class="p">))</span> <span class="n">printf</span><span class="p">(</span><span class="s">&quot;No</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">);</span>
        <span class="k">else</span> <span class="nf">puts</span><span class="p">(</span><span class="s">&quot;Yes&quot;</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>以上.</p>
<p>By:Wahacer</p>
<p>2017.10.22</p>
<p>1.31</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>